This relates to a method and apparatus for operating a logic program and, in particular, to a method and apparatus for implementing a concurrent logic program.
A logic program is a set of axioms defining relationships between objects. A computation of a logic program is a deduction of the consequences of the axioms. Most logic programming languages require the axioms to be Horn clauses which are axioms having the form: EQU A if B.sub.1 and B.sub.2 and . . . and B.sub.n
This definition requires the axioms to consist only of assertions (i.e., A), denials (i.e., not A) and implications (i.e., A if B.sub.1 and B.sub.2 and . . . and B.sub.n). The first part of a clause (i.e., A) will be referred to as the head or consequence of the clause and the remainder (i.e., B.sub.1 . . . B.sub.n) as the body or the tail or condition or antecedent. We will refer to assertions and denials as facts and implications as rules and any of these may be referred to as a clause or axiom.
Logic programming languages of this type include sequential Prolog, PARLOG, Guarded Horn Clauses, and Concurrent Prolog. Extensive material has been published on logic programming and on these programming languages. See, for example, R. A. Kowalski, Logic for Problem Solving (Elsevier North Holland, 1979); D. H. D. Warren, "An Abstract Prolog Instruction Set", Technical Note 309 (SRI International 1983); C. J. Hogger, Introduction to Logic Programming (Academic Press 1984); W. F. Clocksin and C. S. Mellish, Programming in Prolog (Springer-Verlag, 2d Ed. 1984); T. Conlon, Learning MicroProlog (Addison-Wesley 1985); K. Ueda, "Guarded Horn Clauses", ICOT Technical Report TR-103 (1985); E. Shapiro "Concurent Prolog: A Progress Report" Technical Report CS86-10, Weizmann Institute, Israel (1985); U. Bar-On, "A Distributed Implementation of Flat Concurrent Prolog," Thesis, Dept. of Applied Mathematics, Weizmann Institute, Israel (1986); L. Sterling and E. Shapiro, The Art of Prolog: Advanced Programming Techniques, (MIT Press 1986).
Kowalski realized that Horn clauses could be read both declaratively, saying that A is true if B.sub.1 and B.sub.2 and . . . and B.sub.n are true, and procedurally, saying that to prove the goal A (or execute procedure A or solve problem A) one can prove subgoals (or execute subprocedures or solve subproblems) B.sub.1 and B.sub.2 and . . . and B.sub.n. R. A. Kowalski, Logic for Problem Solving (Elsevier North Holland 1979).
For example, the following program identifies objects X that appear in both lists L1 and L2 (i.e., list intersection):
intersect (X, L1, L2): - member (X, L1) and member (X, L2). PA1 member (X, [X.vertline.Xs]). PA1 member (X, [Y.vertline.Ys]): - member (X, Ys). PA1 A logic program is a finite set of universally quantified axioms. PA1 An execution is the proof of an existential statement from the program. PA1 The basic proof procedure is non-deterministic. PA1 The proof of a goal from a logic program establishes the existence of an instance of the goal which follows from the program and also provides values for the goal variables defining such an instance. These values constitute the output of the computation. There may be many different successful computations of a goal, each resulting in a different output. PA1 likes (john, mary) PA1 likes (robert, susan) PA1 likes (michael, mary) PA1 likes (paul, wendy) PA1 likes (john, wendy) PA1 likes (michael, susan) PA1 likes (robert, wendy) PA1 likes (robert, mary) PA1 a process in concurrent programming can be analogized to a goal in sequential Prolog; PA1 a network of processes can be analogized to a conjunction of goals PA1 a communication channel between processes or a variable shared by several processes can be analogized to a logical variable shared between two or more goals; PA1 rules or instructions for process behavior can be analogized to the clauses of a logic program.
Read declaratively, the first axiom reads: X is in the intersection of list L1 and L2 if X is a member of list L1 and X is a member of list L2. Read procedurally, the first axiom reads: to find an X in the intersection of lists L1 and L2, find an X which is a member of L1 and also a member of L2. The term [X.vertline.Xs] is standard list notation denoting a list whose first element is X and whose remaining elements are Xs. The axioms defining "member" read X is a member of the list whose first element is X and X is a member of the list [Y.vertline.Ys] if X is a member of Ys. The determination of membership in a list is a recursive process explained, for example, in Chapter 5 of Learning MicroProlog.
From Kowalski's insight a computational model for logic programs was derived. This model is based on the following principles:
For example, in the list intersection program, let L1 be the list [2,4,6,8,10,12] and L2 the list [3,6,9,12,15]. If we then seek to prove the goal: does there exist an X such that: intersect (X, [2,4,6,8,10,12], [3,6.9,12,15]), the logic program will identify each member of list L1 and seek to establish that such member is identical to a member of list L2. Outputs for this goal will be X=6 and X=12.
The basic computation steps of a logic program proof procedure are (1) the unification of a goal with the head of a clause and (2) its reduction to (or replacement by) the subgoals specified in the body of the clause. The unification procedure is a specialized form of Robinson's resolution principle. J. A. Robinson, "A Machine-oriented Logic Based on the Resolution Principle", Journal of the ACM, vol. 12, pp. 23-41 (1965). Unification of two terms involves finding values that may be substituted for variables in the terms so as to make the two terms identical. See, for example, C. J. Hogger, Introduction to Logic Programming, p.217 (Academic Press 1984). The usual logic program task is to satisfy a conjunction of unsolved goals, which are referred to as the resolvent, by searching a database to locate facts that will unify with a goal. The various logic programming languages approximate the foregoing model and differ mainly in the manner in which the proof of a goal is constructed.
The axioms of a logic programming language are built from terms. A term is either a constant, a variable or a structure. Constants name specific objects or relationships. Variables function as pronouns in that they represent an object that cannot be named. A structure is a single object which consists of a collection of other objects. It is written in the form: f(a,b,c) where f is called the functor or predicate and the terms in parentheses are called components or arguments. A fact is written as a structure specifying a relationship between two or more objects. In such a structure, the relationship is written as the functor or predicate and the objects are written as the components or arguments. Thus the fact "John likes Mary" may be written as: likes (john, mary). A typical query to a database will have the form: ? - f(a,X) where X is a variable representing the sought after information. When it is not known what this variable stands for, the variable is uninstantiated. When the variable does stand for an object, it is instantiated.
The query provides a conjunction of goals to be satisfied. The logic programming language Prolog satisfies these goals in a sequential approximation to the logic programming model using a technique called depth first searching with backtracking. To answer a query, Prolog uses the known clauses in the database to satisfy the goals. A fact can cause a goal to be satisfied immediately if the goal unifies with the fact. A rule can only reduce the task to one of satisfying a conjunction of subgoals and can do so only if the goal unifies with the head of the rule. For example, to answer a query containing one variable, Prolog searches through the database seeking a structure having the same functor and the same components except for the variable in the same positions within the structure. If such a match is found, the variable is instantiated to the object at the corresponding position within the structure.
If a goal cannot be satisfied immediately, backtracking is initiated to find an alternative way to satisfy the goal. Thus, to satisfy a goal, Prolog searches sequentially for the first clause in the database which matches the goal and reduces this goal using that clause. Prolog then tries to solve the reduced goal instantiating variables as it goes. This is called depth first searching. If Prolog ever fails to solve a goal because all the possible clauses for a match have been tried and failed to match, then it backtracks to the last clause chosen and attempts to find an alternative clause for the appropriate goal. As part of this backtracking it uninstantiates all variables that were instantiated in the course of the prior attempt to satisfy the goal.
For example, the database may comprise the facts:
If the query is:
? - likes (X, mary) and likes (X, wendy), the program searches through the database to find the first person who likes Mary. The first fact indicates the John likes Mary and the variable X is instantiated to john. To satisfy the second subgoal, the program then checks to see of John likes Wendy. It locates this fact in the data base and reports that X=john in satisfaction of the query. The program then resets the variable and searches for someone else who likes Mary and Wendy. It locates the fact that Michael likes Mary, and the variable X is instantiated to michael. However, further search of the database does not locate the fact that Michael likes Wendy. According, the program backtracks to the fact that Michael likes Mary, uninstantiates the variable and resumes the search for other facts relating to who likes Mary. Next, it finds the fact that Robert likes Mary and instantiates the variable X to robert. It then locates the fact that Robert likes Wendy and reports that X=robert in satisfaction of the query. At this point the search is done.
The policy for removing and adding goals to the resolvent is called the scheduling policy of the interpreter. Prolog's scheduling policy is to maintain the resolvent as a stack. Instead of arbitrarily removing a goal from the resolvent, the first goal in the resolvent stack is popped. The body of the reducing clause is pushed on the resolvent stack, starting from the last goal in the body.
A nondeterministic choice for a reducing clause is simulated by (1) sequential search through the clauses typically in the order in which they appear in the database and a search through the terms of a clause from left to right and (2) backtracking. When attempting to reduce a goal, the first clause in the program whose head unifies with the goal is chosen. If no unifiable clause is found for the popped goal, the computation is unwound to the last choice made of a clause, and the next unifiable clause is chosen.
As will be apparent, a large database and a complicated conjunction of goals will impose a considerable searching burden on any available serial (von Neumann-type) computer. For this reason, it is desirable to perform such searching of the database in parallel and several concurrent programming languages for doing so are presently being developed.
Concurrent programming languages exploit the parallelism inherent in logic programming using both "And-parallelism" and "Or-parallelism". Specifically, all the goals in the body of a clause are reduced in parallel, which is called "And-parallelism"; and a goal is unified with the heads of all applicable clauses in parallel and the bodies of the clauses whose heads unify are solved in parallel, which is called "Or-parallelism".
As an aid to understanding concurrent programming languages, it is useful to analogize certain elements of concurrent programming to sequential logic programming. In particular,
In contrast to sequential Prolog, an action taken by a process in concurrent Prolog cannot be undone and backtracking is not permitted. Once a process has reduced itself using some clause, it is committed to it.
The resulting computational behavior is called committed choice nondeterminism or indeterminacy. Because of the use of indeterminacy, process synchronization is required to delay an action until enough information is available to ensure that it is a correct one.
Concurrent Prolog uses two synchronization and control constructs: the read-only annotation and the guarded clause. The read-only annotation (indicated by a question mark) can be added to any occurrence of a variable in a logic program, thereby designating it as read-only. A read-only occurrence of a variable cannot be used to instantiate that variable.
A guarded clause has the form: EQU A:-G.sub.1, G.sub.2, . . . G.sub.m .vertline.B.sub.1, B.sub.2, . . . , B.sub.n m,n.gtoreq.O
The commit operator, .vertline. , separates the right hand side of the rule into a guard, G.sub.1, G.sub.2, . . . G.sub.m, and a body, B.sub.1, B.sub.2, . ., B.sub.n. Declaratively, it is read just like a conjunction: A is true if the G's and B's are true. Procedurally, the reduction of a process A.sub.1 using such clauses suspends until A.sub.1 is unifiable with A and the guard is determined to be true. Since the reduction proceeds in parallel, this may be read procedurally as: to solve A, first solve the guards, G.sub.i, in parallel and, if successful, solve the goals in the body, B.sub.j, in parallel. Thus, to satisfy a goal A, the guards of all the clauses in the procedure for A whose heads unify with A are tried in parallel; and when a guard succeeds, this guard commits. The goals in the body of the clause are then executed in parallel.
In concurrent Prolog, the goals, G.sub.i, in the guard can be arbitrary programs and the applicability of a clause for reduction can be arbitrarily complex. In a subset of concurrent Prolog known as flat concurrent Prolog, the goals in the guards can contain calls only to a fixed set of simple test-predicates.
The scheduling policy for concurrent Prolog illustratively is to maintain the resolvent as a first-in-first-out queue, in which goals are removed from the front of the queue and are added at its back. This policy is called breadth-first scheduling.